import java.util.ArrayList;

/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class GenerateParentheses {
	ArrayList<String> res;
	int[] a;
	int n;

	public void search(int dep) {
		if (dep == n / 2) {
			System.out.println("add");
			String s = "";
			for (int i = 0; i < n; ++i) {
				s += (a[i] == 1 ? "(" : ")");
			}
			res.add(s);
			return;
		}
		int i = 0;
		while (a[i] != 0) {
			i++;
		}
		a[i] = 1;
		for (int j = i + 1; j < n; j += 2) {
			if (a[j] == 0) {
				a[j] = -1;
				search(dep + 1);
				a[j] = 0;
			} else {
				break;
			}
		}
		a[i] = 0;
	}

	public ArrayList<String> generateParenthesis(int n) {
		res = new ArrayList<String>();
		this.n = n << 1;
		a = new int[this.n];
		search(0);
		return res;
	}

	public static void main(String[] args) {
		GenerateParentheses a = new GenerateParentheses();
		a.generateParenthesis(2);
	}

}
